一、題目介紹
今天要解的題目是LeetCode的Climbing Stairs

題目描述
假設有一個樓梯，共有n階
每一次可以選擇

• 往上走 1 階
• 往上走 2 階
  問：總共有幾種不同的方法可以爬到樓梯頂端？

例如：n = 2
有兩種走法

• 1 + 1
• 2
  所以答案是2

再例如：n = 3
共有

• 1 + 1 + 1
• 1 + 2
• 2 + 1
  因此答案為3

二、解題思路
這題最重要的是觀察它的規律

假設我們現在站在第n階
要走到第n階，最後一步只有兩種可能

情況一：從第n - 1階走 1 步
n - 1 → n

情況一：從第n - 2階走 2 步
n - 2 → n

所以dp[n] = dp[n - 1] + dp[n - 2]就是這題最重要的狀態轉移公式

三、什麼是Dynamic Programming？
Dynamic Programming，中文通常稱為：動態規劃
簡稱DP

DP的核心概念之一，就是把大問題拆成較小的子問題，並保存已經計算過的結果，避免重複計算。

在Climbing Stairs中
dp[1] = 1
dp[2] = 2

接著
dp[3] = dp[2] + dp[1] = 2 + 1 = 3

再來
dp[4] = dp[3] + dp[2] = 3 + 2 = 5

所以可以得到1, 2, 3, 5, 8, 13, ...
會發現它其實就是非常熟悉的Fibonacci數列

四、為什麼可以使用DP？
這題可以使用Dynamic Programming，主要是因為它具有兩個重要特性

1. 重複子問題
   例如我們想知道dp[5]
   需要知道dp[4]、dp[3]
   而計算其他狀態時，也可能再次需要這些結果
   如果每次都重新計算，就會產生很多重複工作
   DP可以把已經算好的結果保存起來

2. 最佳子結構
   到達第n階的方法，可以由
   到達n-1階的方法以及到達n-2階的方法組合而成
   因此我們可以利用較小問題的答案，建立更大的問題

五、DP陣列解法
最直觀的DP方法，可以建立一個陣列dp[i]
代表：到達第i階共有幾種方法。

初始狀態
dp[1] = 1
dp[2] = 2

狀態轉移
dp[i] = dp[i - 1] + dp[i - 2]

例如 n = 5
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
dp[5] = 8

所以答案為8

六、Java實作

七、Python實作

八、空間最佳化
雖然使用 DP 陣列可以很清楚地理解這題，但仔細觀察會發現
計算dp[i]時，我們其實只需要
dp[i - 1]
dp[i - 2]
不需要保存全部的DP陣列

因此可以只使用兩個變數

• prev2
• prev1
  分別代表前兩個狀態

這樣就可以將空間從O(n)降低到O(1)

九、時間與空間複雜度
時間複雜度O(n)

• 只需要從3走到n

空間複雜度O(n)

• 建立dp陣列

十、Java與Python解法比較

十一、實作結果
Leetcode測試結果：Accepted

十二、今日學習心得
今天開始接觸Dynamic Programming（DP），讓我了解到，有些問題雖然看起來需要不斷重新計算，但其實可以將問題拆成許多較小的子問題，並保存已經得到的結果。

在Climbing Stairs中，我發現到達第n階的方法，其實只與第n-1階和第n-2階有關，

因此可以利用：dp[n] = dp[n - 1] + dp[n - 2]
逐步得到答案。

一開始使用DP陣列時，可以很清楚地看到每一個狀態的結果，但進一步觀察後發現，計算目前狀態時其實只需要前兩個結果，因此可以將空間最佳化成O(1)。

今天最大的收穫是：Dynamic Programming不只是把答案存起來，更重要的是找出「狀態」以及狀態之間的關係。